{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #House Robber IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCapability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打家劫舍 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。</p>\n",
    "\n",
    "<p>由于相邻的房屋装有相互连通的防盗系统，所以小偷 <strong>不会窃取相邻的房屋</strong> 。</p>\n",
    "\n",
    "<p>小偷的 <strong>窃取能力</strong> 定义为他在窃取过程中能从单间房屋中窃取的 <strong>最大金额</strong> 。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> 表示每间房屋存放的现金金额。形式上，从左起第 <code>i</code> 间房屋中放有 <code>nums[i]</code> 美元。</p>\n",
    "\n",
    "<p>另给你一个整数&nbsp;<code>k</code> ，表示窃贼将会窃取的 <strong>最少</strong> 房屋数。小偷总能窃取至少 <code>k</code> 间房屋。</p>\n",
    "\n",
    "<p>返回小偷的 <strong>最小</strong> 窃取能力。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,5,9], k = 2\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "小偷窃取至少 2 间房屋，共有 3 种方式：\n",
    "- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。\n",
    "- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。\n",
    "- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。\n",
    "因此，返回 min(5, 9, 9) = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,7,9,3,1], k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= (nums.length + 1)/2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [house-robber-iv](https://leetcode.cn/problems/house-robber-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [house-robber-iv](https://leetcode.cn/problems/house-robber-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,5,9]\\n2', '[2,7,9,3,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(target: int) -> bool:\n",
    "            arr = [i for i in range(n) if nums[i] <= target]\n",
    "            cnt = 0\n",
    "            prev = -1\n",
    "            for i in arr:\n",
    "                if prev == -1 or prev + 1 != i:\n",
    "                    prev = i\n",
    "                    cnt += 1\n",
    "            return cnt >= k\n",
    "        l, r = min(nums), max(nums)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # 这道题一眼看上不不太会做，但是看了别人的思路，大概明白了\n",
    "        # 和美团笔试的最后一题是差不多的\n",
    "\n",
    "        # 这个函数定义的是，能否，窃取k间房屋，且最大值不超过val\n",
    "        def check(k, val):\n",
    "            n = len(nums)\n",
    "            # dp表示到i户，能窃取的房屋数量\n",
    "            dp = [0] * (n + 1)\n",
    "            dp[1] = 1 if nums[0] <= val else 0\n",
    "            for i in range(1, n):\n",
    "                if nums[i] > val:\n",
    "                    dp[i + 1] = dp[i]\n",
    "                else:\n",
    "                    dp[i + 1] = max(dp[i], dp[i - 1] + 1)\n",
    "            return dp[-1] >= k\n",
    "\n",
    "\n",
    "        # 然后采用二分的方式查找\n",
    "        min_ = 0\n",
    "        max_ = max(nums)\n",
    "        while min_ < max_:\n",
    "            mid_ = int((min_ + max_) / 2)\n",
    "            if check(k, mid_):\n",
    "                max_ = mid_\n",
    "            else:\n",
    "                min_ = mid_ + 1\n",
    "        return min_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        low = 1\n",
    "        high = max(nums)\n",
    "        while low < high:\n",
    "            mid = low + (high - low) // 2#mid代表偷窃能力\n",
    "            pre = -2\n",
    "            count = 0\n",
    "            for i in range(len(nums)):\n",
    "                if i - pre >= 2 and mid >= nums[i]:\n",
    "                    count += 1\n",
    "                    pre = i\n",
    "            if count >= k:\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def check(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx: f0 = f1\n",
    "                else: f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        return bisect_left(range(max(nums)), k, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\r\n",
    "        def check(mx: int) -> int:\r\n",
    "            f0 = f1 = 0\r\n",
    "            for x in nums:\r\n",
    "                if x > mx: f0 = f1\r\n",
    "                else: f0, f1 = f1, max(f1, f0 + 1)\r\n",
    "            return f1\r\n",
    "        return bisect_left(range(max(nums)), k, key=check)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        # solve(mx) 返回最大金额为 mx 时，最多可以偷多少间房子\n",
    "        def solve(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        return bisect_left(range(max(nums)), k, key=solve)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def check(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx: f0 = f1\n",
    "                else: f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        return bisect_left(range(0, max(nums)), k, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        lower, upper = min(nums), max(nums)\n",
    "        while lower < upper:\n",
    "            cnt = 0\n",
    "            visited = False\n",
    "            middle = (lower + upper) // 2\n",
    "            for num in nums:\n",
    "                if num <= middle and not visited:\n",
    "                    cnt += 1\n",
    "                    visited = True\n",
    "                else:\n",
    "                    visited = False\n",
    "            if cnt >= k:\n",
    "                upper = middle\n",
    "            else:\n",
    "                lower = middle + 1\n",
    "        return lower"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        i, j = min(nums), max(nums)\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            l = [i for i, c in enumerate(nums) if c <= mid]\n",
    "            if len(l) < k:\n",
    "                return False\n",
    "            cnt = 1\n",
    "            pre = l[0]\n",
    "            for i in range(1, len(l)):\n",
    "                if l[i] - pre > 1:\n",
    "                    pre = l[i]\n",
    "                    cnt += 1\n",
    "            return cnt >= k\n",
    "\n",
    "        while i < j:\n",
    "            mid = (i + j) // 2\n",
    "            if not check(mid):\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, A: List[int], k: int) -> int:\n",
    "        l, r = min(A), max(A)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            last = take = 0\n",
    "            for a in A:\n",
    "                if last:\n",
    "                    last = 0\n",
    "                    continue\n",
    "                if a <= m:\n",
    "                    take += 1\n",
    "                    last = 1\n",
    "            if take >= k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        l, r = min(nums), max(nums)\n",
    "        while l<=r:\n",
    "            mid = int((l+r)/2)\n",
    "            count,f = 0,False\n",
    "            for x in nums:\n",
    "                if x<=mid and not f:\n",
    "                    count+=1\n",
    "                    f = True\n",
    "                else:\n",
    "                    f = False\n",
    "            if count>=k:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        def ifexist(nums, threshold, k):\n",
    "            front = 0\n",
    "            num = 0\n",
    "            for i in nums:\n",
    "                if (i <= threshold) and (front == 0):\n",
    "                    front = 1\n",
    "                    num = num + 1\n",
    "                else:\n",
    "                    front = 0\n",
    "            if num >= k:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        thres = []\n",
    "        for i in nums:\n",
    "            thres.append(i)\n",
    "\n",
    "        thres.sort()\n",
    "\n",
    "        pointer_l = 0\n",
    "        pointer_r = len(thres) - 1\n",
    "\n",
    "        while 1:\n",
    "            if pointer_l == pointer_r:\n",
    "                break\n",
    "            pointer = int((pointer_l + pointer_r) / 2)\n",
    "\n",
    "            if ifexist(nums, thres[pointer], k) == 1:\n",
    "                pointer_r = pointer\n",
    "            else:\n",
    "                pointer_l = pointer + 1\n",
    "\n",
    "        return(thres[pointer_l])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        min_money, max_money = min(nums), max(nums)\n",
    "\n",
    "        while min_money <= max_money:\n",
    "            mid = (min_money + max_money) // 2\n",
    "            # 统计偷窃金额不超过mid时, 能偷多少房间\n",
    "            count = 0\n",
    "            visited = False\n",
    "            for num in nums:\n",
    "                if num <= mid and visited is False:\n",
    "                    count += 1\n",
    "                    visited = True\n",
    "                else:\n",
    "                    visited = False\n",
    "\n",
    "            if count < k:\n",
    "                min_money = mid+1\n",
    "            else:\n",
    "                max_money = mid-1\n",
    "        return min_money"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        def slove(mid):\n",
    "            l = -1e9\n",
    "            cnt = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                if num <= mid and i - l > 1:\n",
    "                    l = i\n",
    "                    cnt += 1\n",
    "                if cnt >= k:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "        l = 0\n",
    "        r = int(1e9)\n",
    "        ans = 0\n",
    "\n",
    "        while l<=r:\n",
    "            mid = (l+r) >> 1\n",
    "            if slove(mid):\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) <= 2:\n",
    "            nums.sort()\n",
    "            return nums[k-1]\n",
    "        n = len(nums)\n",
    "        def f(a):\n",
    "            last1, last0 = (nums[0]<=a), (min(nums[:2])<=a)\n",
    "            for i in range(2, n):\n",
    "                last1, last0 = last0, max(last0, last1+(nums[i]<=a))\n",
    "            return max(last1, last0)\n",
    "        return bisect_left(range(max(nums)), k, key=f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        def check(x):\n",
    "            if n == 1:\n",
    "                return int(nums[0] <= x)\n",
    "            dp[0] = int(nums[0] <= x)\n",
    "            dp[1] = int(nums[1] <= x) if dp[0] == 0 else 1\n",
    "            for i in range(2, n):\n",
    "                if nums[i] > x: dp[i] = dp[i - 1]\n",
    "                else: dp[i] = max(dp[i - 1], 1 + dp[i - 2])\n",
    "            return dp[n - 1] >= k\n",
    "\n",
    "        left, right = 0, max(nums)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # # 前k个最小值\n",
    "        # # 维护k的最大堆\n",
    "        # hp = [-x for x in nums[:k]]\n",
    "        # heapq.heapify(hp)\n",
    "        # for i in range(k,len(nums)):\n",
    "        #     if -hp[0]>nums[i]:\n",
    "        #         heapq.heappop(hp)\n",
    "        #         heapq.heappush(hp,-nums[i])\n",
    "        # ans = [-x for x in hp]\n",
    "        # print(ans)\n",
    "        # return max(ans)\n",
    "        # 超时 回溯\n",
    "        # res = []\n",
    "        # path = []\n",
    "        # flag = [False]*len(nums)\n",
    "        # def backTracking(nums,startIndex,k,flag):\n",
    "        #     if len(path)==k:\n",
    "        #         res.append(max(path))\n",
    "        #         # print(path)\n",
    "        #         return\n",
    "        #     for i in range(startIndex,len(nums)):\n",
    "        #         if flag[i] or i>0 and flag[i-1]:\n",
    "        #             continue\n",
    "        #         flag[i]=True\n",
    "        #         path.append(nums[i])\n",
    "        #         backTracking(nums,i+1,k,flag)\n",
    "        #         path.pop()\n",
    "        #         flag[i]=False\n",
    "        # backTracking(nums,0,k,flag)\n",
    "        # print(res)\n",
    "        # return min(res)\n",
    "\n",
    "        # 二分\n",
    "        lower = min(nums)\n",
    "        upper = max(nums)\n",
    "        while lower <= upper:\n",
    "            middle = (lower+upper)//2\n",
    "            print(lower)\n",
    "            count = 0\n",
    "            visited = False\n",
    "            for x in nums:\n",
    "                if x <= middle and not visited:\n",
    "                    count += 1\n",
    "                    #print('x'+str(x))\n",
    "                    visited = True\n",
    "                else:\n",
    "                    visited = False\n",
    "            print('count'+str(count))\n",
    "            if count >= k:\n",
    "                upper = middle-1\n",
    "            else:\n",
    "                lower = middle+1\n",
    "        return lower\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def check(mid):\n",
    "            # 判断k是否满足偷至少k个不相邻房屋要求\n",
    "            f0, f1 = 0, 0\n",
    "            for n in nums:\n",
    "                if n <= mid:\n",
    "                    f0, f1 = f1, max(f0+1, f1)\n",
    "                else:\n",
    "                    f0 = f1\n",
    "            if f1 >= k:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        l, r = min(nums), max(nums)  # 窃取能力的范围\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\r\n",
    "        def sovle(mx: int) -> bool:\r\n",
    "            f0 = f1 = 0\r\n",
    "            for x in nums:\r\n",
    "                if (x > mx):\r\n",
    "                    f0 = f1\r\n",
    "                else:\r\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\r\n",
    "            return f1 >= k\r\n",
    "        r = 1000000001\r\n",
    "        l = 0\r\n",
    "        while (l + 1 != r):\r\n",
    "            m = int(l+(r-l)/2)\r\n",
    "            print(m)\r\n",
    "            if (sovle(m)):\r\n",
    "                r = m\r\n",
    "            else:\r\n",
    "                l = m\r\n",
    "        return r\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        max_val, min_val = max(nums), min(nums)\n",
    "        while max_val != min_val:\n",
    "            mid_val = int((min_val + max_val) / 2)\n",
    "            sel = False\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                if num <= mid_val and not sel:\n",
    "                    count += 1\n",
    "                    sel = True\n",
    "                else:\n",
    "                    sel = False\n",
    "            if count >= k:\n",
    "                max_val = mid_val\n",
    "            else:\n",
    "                min_val = mid_val + 1\n",
    "        return min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # 方法2、二分 + dp\n",
    "        def check(uplimit):\n",
    "            dp = [0 for _ in range(n + 1)]\n",
    "            for i in range(1, n + 1):\n",
    "                x = nums[i - 1]\n",
    "                if x <= uplimit:\n",
    "                    dp[i] = max(dp[i - 1], dp[i - 2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            return dp[n] >= k\n",
    "\n",
    "        n = len(nums)\n",
    "        MAX = int(10 ** 9)\n",
    "        l = 1\n",
    "        r = MAX\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) == True:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        def check(nums, k, mx):\n",
    "            n = len(nums)\n",
    "            dp = [0 for _ in range(n)]\n",
    "            if nums[0] <= mx:\n",
    "                dp[0] = 1\n",
    "            if nums[0] <= mx or nums[1] <= mx:\n",
    "                dp[1] = 1\n",
    "            for i in range(2, n):\n",
    "                if nums[i] <= mx:\n",
    "                    dp[i] = max(dp[i-1], dp[i-2]+1)\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]\n",
    "            \n",
    "            return dp[n-1] >= k\n",
    "        \n",
    "        \n",
    "        max_val = max(nums)\n",
    "        l , r = 0, max_val\n",
    "        while l <= r:\n",
    "            mid = l + (r-l)//2\n",
    "            if check(nums, k, mid):\n",
    "                r = mid-1\n",
    "            else:\n",
    "                l = mid+1\n",
    "        \n",
    "        if check(nums, k, l):\n",
    "            return l\n",
    "        else:\n",
    "            return l+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        maxNum = nums[0]\n",
    "        for num in nums:\n",
    "            maxNum = max(maxNum, num)\n",
    "        l, r = 0, maxNum + 1\n",
    "        n = len(nums)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            d = [0 for i in range(n)]\n",
    "            lastTaken = False\n",
    "            if nums[0] <= m:\n",
    "                d[0] = 1\n",
    "                lastTaken = True\n",
    "            for i in range(1, n):\n",
    "                if nums[i] > m:\n",
    "                    d[i] = d[i - 1]\n",
    "                    lastTaken = False\n",
    "                elif lastTaken:\n",
    "                    d[i] = d[i - 1]\n",
    "                    lastTaken = False\n",
    "                else:\n",
    "                    d[i] = d[i - 1] + 1\n",
    "                    lastTaken = True\n",
    "            if d[n - 1] >= k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # exception case\n",
    "        assert isinstance(nums, list) and len(nums) >= 1\n",
    "        assert isinstance(k, int) and k >= 1\n",
    "        # main method: (Binary Search - Dynamic Programming)\n",
    "        return self._minCapability(nums, k)\n",
    "\n",
    "    def _minCapability(self, nums: List[int], k: int) -> int:\n",
    "        assert isinstance(nums, list) and len(nums) >= 1\n",
    "        assert isinstance(k, int) and k >= 1\n",
    "\n",
    "        def __check(target: int) -> bool:\n",
    "            count = 0\n",
    "            i = 0\n",
    "            while i < len(nums):\n",
    "                if nums[i] <= target:\n",
    "                    count += 1\n",
    "                    i += 1\n",
    "                i += 1\n",
    "            return count >= k\n",
    "\n",
    "        left = min(nums)\n",
    "        right = max(nums)\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            # mid = left + ((right - left) >> 1)\n",
    "            mid = (left + right) >> 1\n",
    "            if __check(mid):\n",
    "                res = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def ok(mid):\n",
    "            if n == 1:\n",
    "                return 1 if nums[0] <= mid else 0\n",
    "            if n == 2:\n",
    "                return 1 if nums[0] <= mid or nums[1] <= mid else 0\n",
    "            dp = [0 for _ in range(n)]\n",
    "            dp[0] = 1 if nums[0] <= mid else 0\n",
    "            dp[1] = 1 if nums[0] <= mid or nums[1] <= mid else 0\n",
    "            for i in range(2, n):\n",
    "                dp[i] = max(dp[i-1], dp[i-2] + (1 if nums[i] <= mid else 0))\n",
    "            return dp[n-1]\n",
    "        l = 0\n",
    "        r = max(nums)\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            if ok(mid) >= k:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def ok(mid):\n",
    "            if n == 1:\n",
    "                return 1 if nums[0] <= mid else 0\n",
    "            if n == 2:\n",
    "                return 1 if nums[0] <= mid or nums[1] <= mid else 0\n",
    "            dp = [0 for _ in range(n)]\n",
    "            dp[0] = 1 if nums[0] <= mid else 0\n",
    "            dp[1] = 1 if nums[0] <= mid or nums[1] <= mid else 0\n",
    "            for i in range(2, n):\n",
    "                dp[i] = max(dp[i-1], dp[i-2] + (1 if nums[i] <= mid else 0))\n",
    "            return dp[n-1]\n",
    "        l = 0\n",
    "        r = max(nums)\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            if ok(mid) >= k:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        l, r = min(nums), max(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            count = 0\n",
    "            visited = False\n",
    "            for num in nums:\n",
    "                if num <= mid and not visited:\n",
    "                    count += 1\n",
    "                    visited = True\n",
    "                else:\n",
    "                    visited = False\n",
    "            if count >= k :\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        INF = 10 ** 9\n",
    "        \n",
    "        def check(uplimit: int) -> bool:\n",
    "            dp = [0 for _ in range(n + 1)]\n",
    "            for i in range(1, n + 1):\n",
    "                x = nums[i - 1]\n",
    "                if x <= uplimit:\n",
    "                    dp[i] = max(dp[i - 1], dp[i - 2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            return dp[n] >= k\n",
    "        \n",
    "        \n",
    "        # 至少k间。最优就一定是k间。\n",
    "        l = 1\n",
    "        r = INF\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) == True:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # 对小偷的窃取能力进行遍历分析\n",
    "\n",
    "        def check(mx):\n",
    "            n = len(nums) # dp表示在该窃取能力下能偷的房间总数\n",
    "            if n == 1: return 1\n",
    "            dp = [0 for _ in range(n)]\n",
    "            dp[0] = 1 if nums[0] <= mx else 0\n",
    "            dp[1] = 1 if nums[1] <= mx or nums[0] <= mx else 0\n",
    "            for i in range(2, n):\n",
    "                if nums[i] <= mx:\n",
    "                    dp[i] = max(dp[i - 2] + 1, dp[i - 1])\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            return dp[-1]\n",
    "        \n",
    "        left, right = min(nums), max(nums) # 遍历窃取能力\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) >= k: # 左边值全都小于，右边值全都大于或等于\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "\n",
    "        ## 最小化最大值\n",
    "        ## 窃取能力定义为窃取房屋金额的最大值\n",
    "        ## 窃取能力为mx，是否能至少窃取k个房屋，这k个房屋的最大值需要<=mx\n",
    "        # def solve(mx, k):\n",
    "        #     f0 = f1 = 0\n",
    "        #     for x in nums:\n",
    "        #         if x > mx:\n",
    "        #             f0 = f1\n",
    "        #         else:\n",
    "        #             f0, f1 = f1, max(f1, f0 + 1)\n",
    "        #     return f1 >= k\n",
    "        def solve(mx, k):\n",
    "            n = len(nums)\n",
    "            dp = [0 for _ in range(n)]\n",
    "            # dp[i] = max(dp[i-1], dp[i-2] + 1)\n",
    "            if nums[0] <= mx:\n",
    "                dp[0] = 1\n",
    "            if nums[1] <= mx:\n",
    "                dp[1] = max(dp[0], 1)\n",
    "            else:\n",
    "                dp[1] = dp[0]\n",
    "            for i in range(2, n):\n",
    "                if nums[i] <= mx:\n",
    "                    dp[i] = max(dp[i-1], dp[i-2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]\n",
    "            return dp[n-1] >= k\n",
    "\n",
    "        # 二分查找\n",
    "        n = len(nums)\n",
    "        left = min(nums)\n",
    "        right = max(nums)\n",
    "        while(left < right):\n",
    "            mid = left + (right - left)//2\n",
    "            if(not solve(mid, k)):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        return left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def test(element):\n",
    "            l = [False for i in range(len(nums))]\n",
    "            l[0] = (nums[0]<=element)\n",
    "            m=int(l[0])\n",
    "            for i in range(1,len(nums)):\n",
    "                if nums[i]<=element and l[i-1]==False:\n",
    "                    m+=1\n",
    "                    l[i]=True\n",
    "            # print(m)\n",
    "            return m>=k\n",
    "        mm = nums[:]\n",
    "        mm.sort()\n",
    "        # print(mm)\n",
    "        left = 0\n",
    "        mid = int((len(nums)-1)/2)\n",
    "        right = len(nums)-1\n",
    "        while mid<right:\n",
    "            print(mid)\n",
    "            if test(mm[mid]):\n",
    "                right = mid\n",
    "                mid = int((right-left)/2)+left\n",
    "            else:\n",
    "                left = mid+1\n",
    "                mid = int((right-left)/2)+left\n",
    "        return mm[mid]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def check(cur_val):\n",
    "            pre = -1\n",
    "            can_get = 0\n",
    "            for i in range(len(nums)):\n",
    "                num = nums[i]\n",
    "                if num <= cur_val and (pre == -1 or pre + 1 < i):\n",
    "                    can_get += 1\n",
    "                    pre = i\n",
    "            print(cur_val, can_get)\n",
    "            return can_get\n",
    "        \n",
    "        left = min(nums)\n",
    "        right = max(nums)\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) < k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        if check(left) >= k:\n",
    "            return left\n",
    "        elif check(right) >= k:\n",
    "            return right\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        left = min(nums)\n",
    "        right = max(nums)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            pre = False\n",
    "            cnt = 0\n",
    "            for v in nums:\n",
    "                if v <= mid and not pre:\n",
    "                    pre = True\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    pre = False\n",
    "            \n",
    "            if cnt >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left\n",
    "\"\"\"首先，窃贼的能力值越高，成功的可能性就越大，因此本题可以使用二分法来找所需的最小窃取能力值。\n",
    "\n",
    "另一方面，由于本题并不在意窃取的总金额，而是只需要保证窃取的房子数量，因此在这里可以使用贪心法来进行窃取，也就是一趟遍历，若当前的房子可以窃取，那么就执行窃取。\n",
    "\n",
    "根据上面两个结论，就可以二分答案，二分的上下界自然是房屋金额的最小值和最大值。\n",
    "\n",
    "对于当前二分到的mid，遍历nums数组，同时使用一个变量pre记录上一间房子是否窃取。对于当前遍历到的房屋金额nums[index]，若其小于等于mid，同时pre为false，那么就窃取这间房子，并更新pre为true，否则无法窃取这间房子，此时应该更新pre为false。\n",
    "\n",
    "若最终窃取的房子数量超过了k，那么就调整二分上界为mid，否则调整二分下界为mid + 1。\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def check(x: int) -> bool:\n",
    "            f = [0 for _ in range(len(nums))]\n",
    "            if x >= nums[0]: f[0] = 1\n",
    "            if x >= nums[1]: f[1] = 1\n",
    "            f[1] = max(f[1], f[0])\n",
    "            for i in range(2, n):\n",
    "                f[i] = f[i - 1]\n",
    "                if x >= nums[i]:\n",
    "                    f[i] = max(f[i - 2] + 1, f[i])\n",
    "            return True if f[-1] >= k else False\n",
    "        l, r = min(nums), max(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # 方法2、二分 + dp\n",
    "        def check(uplimit):\n",
    "            dp = [0 for _ in range(n + 1)]\n",
    "            for i in range(1, n + 1):\n",
    "                x = nums[i - 1]\n",
    "                if x <= uplimit:\n",
    "                    dp[i] = max(dp[i - 1], dp[i - 2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            return dp[n] >= k\n",
    "\n",
    "        n = len(nums)\n",
    "        MAX = int(10 ** 9)\n",
    "        l = 1\n",
    "        r = MAX\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) == True:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minCapability(self, nums: List[int], k: int) -> int:\n",
    "#         # 在选择的数值不超过a的情况能够选取最多的房屋\n",
    "#         def f(a):\n",
    "#             dp = [[0, 0] for _ in range(len(nums)+1)]\n",
    "#             for i, n in enumerate(nums):\n",
    "#                 if n <= a:\n",
    "#                     dp[i+1][0] = dp[i][1]\n",
    "#                     dp[i+1][1] = dp[i][0] + 1\n",
    "#                 else:\n",
    "#                     dp[i+1][0] = max(dp[i][0], dp[i][1])\n",
    "#             return max(dp[-1])\n",
    "            \n",
    "#         arr = sorted(nums)\n",
    "#         l, r = 0, len(nums)-1\n",
    "#         while l < r:\n",
    "#             mid = (r+l)//2\n",
    "#             if f(arr[mid]) < k:\n",
    "#                 l = mid + 1\n",
    "#             else:\n",
    "#                 r = mid\n",
    "\n",
    "#         return arr[l]\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        INF = 10 ** 9\n",
    "        \n",
    "        def check(uplimit: int) -> bool:\n",
    "            dp = [0 for _ in range(n + 1)]\n",
    "            for i in range(1, n + 1):\n",
    "                x = nums[i - 1]\n",
    "                if x <= uplimit:\n",
    "                    dp[i] = max(dp[i - 1], dp[i - 2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            return dp[n] >= k\n",
    "        \n",
    "        \n",
    "        # 至少k间。最优就一定是k间。\n",
    "        l = 1\n",
    "        r = INF\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) == True:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def check(nums, k, maxV):\n",
    "            prev = False\n",
    "            i = 0\n",
    "            for num in nums:\n",
    "                if prev:\n",
    "                    prev = False\n",
    "                    continue\n",
    "                elif num <= maxV:\n",
    "                    prev = True\n",
    "                    i += 1\n",
    "                    if i == k:\n",
    "                        return True\n",
    "            return False\n",
    "            # return False\n",
    "        left, right = min(nums), max(nums)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            # print(mid, check(nums, k, mid))\n",
    "            if check(nums, k, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        print(left, right)\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        def check(mx):\n",
    "            dp = [0 for _ in range(n)]\n",
    "            if nums[0] <= mx:\n",
    "                dp[0] = 1\n",
    "            else :\n",
    "                dp[0] = 0\n",
    "            if min(nums[0], nums[1]) <= mx:\n",
    "                dp[1] = 1\n",
    "            else : \n",
    "                dp[1] = 0\n",
    "            for i in range(2, n):\n",
    "                if nums[i] <= mx:\n",
    "                    dp[i] = max(dp[i-2]+ 1, dp[i-1])\n",
    "                else : \n",
    "                    dp[i] = dp[i-1]\n",
    "            return dp[-1]\n",
    "\n",
    "        left, right = 0, max(nums)\n",
    "        while left < right: \n",
    "            mid = left + (right - left) // 2\n",
    "            # print(mid)\n",
    "            if check(mid) >= k:\n",
    "                right = mid\n",
    "            else : \n",
    "                left = mid + 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def check(x):\n",
    "            dp = []\n",
    "            for n in nums:\n",
    "                if n <= x:\n",
    "                    if not dp: dp.append(1)\n",
    "                    else:\n",
    "                        if len(dp) >= 2:\n",
    "                            dp.append(max(dp[-1], 1 + dp[-2]))\n",
    "                        else:\n",
    "                            dp.append(1)\n",
    "                else:\n",
    "                    if not dp: dp.append(0)\n",
    "                    else: dp.append(dp[-1])\n",
    "            return dp[-1] >= k\n",
    "        lo = 0\n",
    "        hi = max(nums) + 1\n",
    "        while lo < hi:\n",
    "            x = (lo + hi) // 2\n",
    "            if check(x):\n",
    "                hi = x\n",
    "            else:\n",
    "                lo = x + 1\n",
    "        return hi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def fun(max_):\n",
    "            pre=cur=0\n",
    "            for num in nums:\n",
    "                if num<=max_: pre,cur = cur,max(cur,pre+1)\n",
    "                else: pre = cur\n",
    "            return cur>=k\n",
    "        left,right = 0,max(nums)\n",
    "        while left+1<right:\n",
    "            mid = (left+right)>>1\n",
    "            if fun(mid): right = mid\n",
    "            else: left = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # solve(mx) 返回最大金额为 mx 时，最多可以偷多少间房子\n",
    "        def solve(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        return bisect_left(range(max(nums)), k, key=solve)\n",
    "\n",
    "\"\"\"\n",
    "不懂\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def solve(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        # 因为「偷走的最大金额」越小，能偷的房子就越少，反之越多。\n",
    "        # [0, max(nums)]二分查找,依次代入solve,返回的值和k做对比\n",
    "        # [return1, return2, k, return3,...] return2<k<=return3\n",
    "        # 返回此时的num\n",
    "        return bisect_left(range(max(nums)), k, key=solve)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n=len(nums)\n",
    "        def check(mid):\n",
    "            dp=[0]*(n+1)\n",
    "            dp[1]=nums[0]<=mid\n",
    "            for i in range(1,n):\n",
    "                dp[i+1]=dp[i]\n",
    "                if nums[i]<=mid:dp[i+1]=max(dp[i+1],dp[i-1]+1)\n",
    "            \n",
    "            return dp[-1]>=k\n",
    "        \n",
    "        l,r=0,max(nums)\n",
    "        while l<r:\n",
    "            mid=l+r>>1\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def solve(mx: int) -> int:\n",
    "            cnt = i = 0\n",
    "            while i < len(nums):\n",
    "                if nums[i] > mx:  # 不偷\n",
    "                    i += 1\n",
    "                else:  # 立刻偷\n",
    "                    cnt += 1\n",
    "                    i += 2  # 跳过下一间房子\n",
    "            return cnt\n",
    "        return bisect_left(range(max(nums)), k, key=solve)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        lower = min(nums)\n",
    "        upper = max(nums)\n",
    "\n",
    "        while lower <= upper:\n",
    "            conut = 0\n",
    "            middle = (lower + upper) // 2\n",
    "            visited = False\n",
    "            \n",
    "            for x in nums:\n",
    "                if x <= middle and not visited:\n",
    "                    conut += 1\n",
    "                    visited = True\n",
    "                else:\n",
    "                    visited = False\n",
    "\n",
    "            if conut >= k:\n",
    "                upper = middle - 1\n",
    "            else:\n",
    "                lower = middle + 1\n",
    "\n",
    "        return lower\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        l, r = min(nums)-1, max(nums)\n",
    "        while (l+1 < r):\n",
    "            mid = (l+r)//2\n",
    "            ct = 0\n",
    "            prev = 0\n",
    "            for n in nums: \n",
    "                if (not prev and n<=mid):\n",
    "                    ct+=1\n",
    "                    prev = 1\n",
    "                elif (prev):\n",
    "                    prev = 0\n",
    "            if (ct>=k): r=mid\n",
    "            else: l=mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        t = sorted(nums)\n",
    "        def check(x):\n",
    "            val = t[x]\n",
    "            cnt = 0\n",
    "            pre = -1\n",
    "            for i in range(n):\n",
    "                if nums[i] <= val and (i - pre > 1 or pre == -1):\n",
    "                    cnt += 1\n",
    "                    pre = i\n",
    "            return cnt >= k\n",
    "        # print(t)\n",
    "        l, r = 0, n - 1\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            \n",
    "            if check(mid):\n",
    "                ans = t[mid]\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def trans(min_max_v):\n",
    "            selected_num = 0\n",
    "            front_select = False\n",
    "            for x in nums:\n",
    "                if x > min_max_v: \n",
    "                    selected_num = selected_num\n",
    "                    front_select = False\n",
    "                else:\n",
    "                    if front_select:\n",
    "                        selected_num = selected_num\n",
    "                        front_select = False\n",
    "                    else:\n",
    "                        selected_num += 1\n",
    "                        front_select = True\n",
    "            return selected_num >= k                    \n",
    "\n",
    "        return bisect_left(range(max(nums)), True, key=trans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # solve(mx) 返回最大金额为 mx 时，最多可以偷多少间房子\n",
    "        def solve(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "\n",
    "        a = range(max(nums))\n",
    "        return bisect_left(range(max(nums)), k, key=solve)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # solve(mx) 返回最大金额为 mx 时，最多可以偷多少间房子\n",
    "        def solve(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        \"\"\"\n",
    "        ls = list(range(max(nums)))\n",
    "        dp = []\n",
    "        for i in ls:\n",
    "            dp.append(solve(i))\n",
    "        # ans = bisect_left(dp, k)\n",
    "        # return ans\n",
    "        \"\"\"\n",
    "        return bisect_left(range(max(nums)), k, key=solve)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#打家劫舍 IV，动态规划\n",
    "#输入：nums = [2,3,5,9], k = 2；输出：5，输入：nums = [2,7,9,3,1], k = 2，输出：2\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        #二分+dp，\n",
    "        def solve(mx):#返回最大金额为mx时，最多可以偷多少间房子\n",
    "            f0=f1=0\n",
    "            for x in nums:\n",
    "                if x>mx:f0=f1\n",
    "                else:f0,f1=f1,max(f1,f0+1)\n",
    "            return f1 \n",
    "        return bisect_left(range(max(nums)),k,key=solve)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # 二分查找，窃取能力的左右边界初始为最小金额和最大金额\n",
    "        l, r = min(nums), max(nums)\n",
    "        # 二分查找，搜索区间左右闭合[left, right]\n",
    "        result = 0\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if self.check(nums, m, k):# 窃取能力为m时，能满足偷至少k间房屋\n",
    "                result = m  # 这是一个潜在的答案，记录\n",
    "                r = m - 1 # 缩小右边界以寻找更小的窃取能力\n",
    "            else: # 窃取能力为m时，不满足偷至少k间房屋\n",
    "                l = m + 1 # 增大左边界提高窃取能力从而提高偷的房屋数量\n",
    "        return result\n",
    "\n",
    "    # 判断窃取能力为amount时，能偷的房屋数是否满足至少k间房屋\n",
    "    def check(self, nums, amount, k):\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while i < len(nums):\n",
    "            if nums[i] <= amount:\n",
    "                count += 1\n",
    "                i += 1\n",
    "            i += 1 # 不要忘记相邻房间如果同时被偷就会报警\n",
    "        return count >= k "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def check(x):\n",
    "            f = [0]*n\n",
    "            f[0] = 1 if nums[0] <= x else 0\n",
    "            if n == 1: return f[0] >= k\n",
    "            f[1] = 1 if nums[1] <= x else f[0]\n",
    "            for i in range(2, n):\n",
    "                f[i] = f[i-1]\n",
    "                if nums[i] <= x: f[i] = max(f[i],f[i-2] + 1)\n",
    "            return max(f) >= k\n",
    "\n",
    "        \n",
    "        l,r = 0, int(1e9)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid): r = mid\n",
    "            else: l = mid + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def ok(mid):\n",
    "            ans1 = 0\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                if nums[i] <= mid:\n",
    "                    ans1 += 1\n",
    "                    i += 1\n",
    "                i += 1\n",
    "            return ans1\n",
    "        l = 0\n",
    "        r = max(nums)\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            if ok(mid) >= k:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        newnums = sorted(nums)\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [0] * (n + 1) #nums[0 - i] 中偷金额不超过mid的房屋，最多能偷多少间，如果dp[n - 1] >= k，表示答案至多为mid，否则表示答案必须超过mid\n",
    "        def solve(mid): #房间金额最大值为mid时最多可偷多少间房间\n",
    "            \n",
    "            dp[0] = 0 if nums[0] > mid else 1\n",
    "            dp[1] = max(0 if nums[1] > mid else 1, dp[0])\n",
    "            for i in range(2, n):\n",
    "                if nums[i] <= mid:\n",
    "                    dp[i] = max(dp[i - 1], dp[i - 2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            \n",
    "            return dp[n - 1]\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2    \n",
    "            res = solve(newnums[mid])\n",
    "            if res < k:\n",
    "                l = mid + 1\n",
    "            elif res >= k:\n",
    "                r = mid - 1\n",
    "        return newnums[l]\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def check(x: int):\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                if cnt >= k:\n",
    "                    return True\n",
    "                if nums[i] <= x:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return cnt >= k\n",
    "\n",
    "        l, r = 0, max(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        left, right = min(nums), max(nums)\n",
    "        n = len(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            idx = 0\n",
    "            count = 0\n",
    "            while idx < n:\n",
    "                if nums[idx] <= mid:\n",
    "                    count += 1\n",
    "                    idx += 1\n",
    "                idx += 1\n",
    "            if count >= k:\n",
    "                right = mid - 1\n",
    "            elif count < k:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # solve(mx) 返回最大金额为 mx 时，最多可以偷多少间房子\n",
    "        def solve(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        return bisect_left(range(max(nums)), k, key=solve)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y : int) -> int:\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        newnums = sorted(nums)\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [0] * (n + 1) #nums[0 - i] 中偷金额不超过mid的房屋，最多能偷多少间，如果dp[n - 1] >= k，表示答案至多为mid，否则表示答案必须超过mid\n",
    "        def solve(mid): #房间金额最大值为mid时最多可偷多少间房间\n",
    "            \n",
    "            dp[0] = 0 if nums[0] > mid else 1\n",
    "            dp[1] = max(0 if nums[1] > mid else 1, dp[0])\n",
    "            for i in range(2, n):\n",
    "                if nums[i] <= mid:\n",
    "                    dp[i] = max(dp[i - 1], dp[i - 2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            \n",
    "            return dp[n - 1]\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            \n",
    "            res = solve(newnums[mid])\n",
    "            #print(\"binary: \", newnums[mid], res)\n",
    "            #if res == k:\n",
    "            #    return newnums[mid]\n",
    "            if res < k:\n",
    "                l = mid + 1\n",
    "            elif res >= k:\n",
    "                r = mid - 1\n",
    "        return newnums[l]\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def func(power: int, k: int) -> bool:\n",
    "            n = len(nums)\n",
    "            if n == 1:\n",
    "                return 1 if nums[0] <= power else 0\n",
    "            if n == 2:\n",
    "                return 1 if nums[0] <= power or nums[1] <= power else 0\n",
    "            dp0 = 1 if nums[0] <= power else 0\n",
    "            dp1 = 1 if nums[0] <= power or nums[1] <= power else 0\n",
    "            for i in range(2, n):\n",
    "                dp0, dp1 = dp1, max(dp1, dp0 + (1 if nums[i] <= power else 0))\n",
    "            return dp1 >= k\n",
    "        left = min(nums) - 1\n",
    "        right = max(nums) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if func(mid, k):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def robberNum(x):\n",
    "            dp = [0] * n \n",
    "    \n",
    "            if nums[0] <= x:\n",
    "                dp[0] = 1\n",
    "\n",
    "            if n == 1:\n",
    "                return dp[0]\n",
    "\n",
    "            if n > 1:\n",
    "                dp[1] = 1 if dp[0] or nums[1] <= x else 0\n",
    "\n",
    "            for i in range(2, n):\n",
    "                dp[i] = max(dp[i-1], dp[i-2] + (1 if nums[i] <= x else 0))\n",
    "\n",
    "            return dp[-1]\n",
    "\n",
    "        l = 0\n",
    "        r = max(nums)\n",
    "\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if robberNum(m) >= k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "\n",
    "        return r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        newnums = sorted(nums)\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [0] * (n + 1) #nums[0 - i] 中偷金额不超过mid的房屋，最多能偷多少间，如果dp[n - 1] >= k，表示答案至多为mid，否则表示答案必须超过mid\n",
    "        def solve(mid): #房间金额最大值为mid时最多可偷多少间房间\n",
    "            \n",
    "            dp[0] = 0 if nums[0] > mid else 1\n",
    "            dp[1] = max(0 if nums[1] > mid else 1, dp[0])\n",
    "            for i in range(2, n):\n",
    "                if nums[i] <= mid:\n",
    "                    dp[i] = max(dp[i - 1], dp[i - 2] + 1)\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1]\n",
    "            \n",
    "            return dp[n - 1]\n",
    "\n",
    "        def solve2(mx):\n",
    "            f0 = f1 = 0\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2    \n",
    "            res = solve2(newnums[mid])\n",
    "            if res < k:\n",
    "                l = mid + 1\n",
    "            elif res >= k:\n",
    "                r = mid - 1\n",
    "        return newnums[l]\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        right = max(nums)\n",
    "        asn = right\n",
    "\n",
    "        def valid(target: int) -> bool:\n",
    "            count = 0\n",
    "            cntable = True\n",
    "            for num in nums:\n",
    "                if num <= target and cntable == True:\n",
    "                    count += 1\n",
    "                    cntable = False\n",
    "                else:\n",
    "                    cntable = True\n",
    "            return count >= k\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if valid(mid):\n",
    "                asn = mid\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return asn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(nums,n,ability):\n",
    "            if n==1:\n",
    "                return 1 if ability>=nums[0] else 0\n",
    "            if n==2:\n",
    "                return 1 if (ability>=nums[0] or ability>=nums[1]) else 0\n",
    "            # dp = [0]*n\n",
    "            prepre = 1 if ability>=nums[0] else 0\n",
    "            pre = 1 if (ability>=nums[0] or ability>=nums[1]) else 0\n",
    "            for i in range(2,n):\n",
    "                if nums[i]<=ability:\n",
    "                    cur = max(pre,1+prepre)\n",
    "                else:\n",
    "                    cur = max(pre,prepre)\n",
    "                prepre = pre\n",
    "                pre = cur\n",
    "            return cur\n",
    "        l = min(nums)\n",
    "        r = max(nums)\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            if f(nums,n,m)>=k:\n",
    "                ans = m\n",
    "                r = m-1\n",
    "            else:\n",
    "                l = m+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        判断窃取能力为y时，能偷的房屋数是否满足至少k间房屋\n",
    "        '''\n",
    "        def check(y: int) -> bool:\n",
    "            count = 0\n",
    "            i = 0\n",
    "            while i < len(nums):\n",
    "                if nums[i] <= y:\n",
    "                    count += 1\n",
    "                    i += 1\n",
    "                i += 1\n",
    "            return count >= k\n",
    "    \n",
    "        # 二分查找，窃取能力的左右边界初始为最小金额和最大金额\n",
    "        left = min(nums)\n",
    "        right = max(nums)\n",
    "        # 二分查找，搜索区间左右闭合[left, right]\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            if check(mid):   # 窃取能力为mid时，能满足偷至少k间房屋\n",
    "                res = mid  # 这是一个潜在的答案，记录\n",
    "                right = mid - 1    # 缩小右边界以寻找更小的窃取能力\n",
    "            else:  # 窃取能力为mid时，不满足偷至少k间房屋\n",
    "                left = mid + 1 # 增大左边界提高窃取能力从而提高偷的房屋数量\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def check(money):\n",
    "            n = len(nums)\n",
    "            dp = [0 for _ in range(len(nums)+1)]\n",
    "            if nums[0]<=money:dp[1]=1\n",
    "            for i in range(2, n+1):\n",
    "                if nums[i-1]>money:\n",
    "                    dp[i]=dp[i-1]\n",
    "                else:\n",
    "                    dp[i]=max(dp[i-1],dp[i-2]+1)\n",
    "            # return dp\n",
    "            return dp[n]>=k\n",
    "        # t = check(3)\n",
    "        # return t\n",
    "        num = nums[:]\n",
    "        num.sort()\n",
    "        l, r = -1, len(num)\n",
    "        while l+1!=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(num[mid]):\n",
    "                r = mid\n",
    "            else:\n",
    "                l =mid\n",
    "        return num[r]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def f(y):\n",
    "            count, visited = 0, False\n",
    "            for x in nums:\n",
    "                if x <= y and not visited:\n",
    "                    count, visited = count + 1, True\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "            \n",
    "        return bisect_left(range(min(nums), max(nums)), k, key = f) + min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        left, right = min(nums), max(nums)\n",
    "        n = len(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            idx = 0\n",
    "            count = 0\n",
    "            while idx < n:\n",
    "                if nums[idx] <= mid:\n",
    "                    count += 1\n",
    "                    idx += 1\n",
    "                idx += 1\n",
    "            if count >= k:\n",
    "                right = mid - 1\n",
    "            elif count < k:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # 题目要计算最大值的最小值，二分答案。\n",
    "        # 因为至少要偷k个房子，需要为后续的房子预留空间\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(limit):\n",
    "            # 偷窃值不能大于limit\n",
    "            # 最少要偷k个房子\n",
    "            pos = 0\n",
    "            remain = k\n",
    "            while pos<n and remain>0:\n",
    "                while pos<=n-2*remain+1 and nums[pos]>limit:\n",
    "                    pos+=1\n",
    "                if pos<=n-2*remain+1:\n",
    "                    remain -= 1\n",
    "                    pos += 2\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        l,r = 1, max(nums)\n",
    "        ans = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        def numsOfHouses(money: int) -> int:\n",
    "            visited, count = False, 0\n",
    "            for x in nums:\n",
    "                if x <= money and visited is False:\n",
    "                    visited, count = True, count + 1\n",
    "                else:\n",
    "                    visited = False\n",
    "            return count\n",
    "\n",
    "        left, right = min(nums), max(nums)\n",
    "        while left <= right:\n",
    "            middle = math.floor((left + right) / 2)\n",
    "            if numsOfHouses(middle) >= k:\n",
    "                right = middle - 1\n",
    "            else:\n",
    "                left = middle + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        # solve(mx) 返回最大金额为 mx 时，最多可以偷多少间房子\n",
    "        def solve(mx: int) -> int:\n",
    "            f0 = f1 = 0\n",
    "            # f0代表不考虑当前房屋时，小偷窃取的最多的房屋数 \n",
    "            # f1代表考虑当前房屋时 ，小偷窃取的最多的房屋数\n",
    "            for x in nums:\n",
    "                if x > mx:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f1, f0 + 1)\n",
    "            return f1\n",
    "        # 查找第一个使solve(mx) >= k成立的mx值。\n",
    "        # 通过循环查找第一个使solve(mx) >= k成立的mx值。\n",
    "        left, right = 0, max(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if solve(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "nums = [2,3,5,9]  # 输出：5\n",
    "k = 2\n",
    "Solution(). minCapability(nums, k)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
